目前已知的梅森素数(Mersenne primes)
形如 $2^n-1$ 的数, 如果是素数, 则称为梅森素数(Mersenne prime).
由于当 $n$ 是合数时, 比如 $n=pq$, 则 $2^{pq}-1$ 总可以分解. 具体的, 若 $q=2k$, 则有 $2^{2pk}-1=(2^{pk}-1)(2^{pk}+1)$. 若 $q=2k+1$, 则含有因子 $2^p-1$. 因此 $2^n-1$ 称为素数的必要条件是 $n$ 是素数.
一般记梅森素数为 $M_p=2^p-1$, 其中 $p$ 为素数. 目前已知的梅森素数有
| No. | $p$ | $M_p$ | isPrime |
|---|---|---|---|
| 1 | 2 | $2^2-1=3$ | Y |
| 2 | 3 | $2^3-1=7$ | Y |
| 3 | 5 | $2^5-1=31$ | Y |
| 4 | 7 | $2^7-1=127$ | Y |
| 11 | $2^{11}-1=2047$ | N | |
| 5 | 13 | $2^{13}-1=8191$ | Y |
| 6 | 17 | $2^{17}-1=131071$ | Y |
| 7 | 19 | $2^{19}-1=524287$ | Y |
| 23 | $2^{23}-1=8388607$ | N | |
| 29 | $2^{29}-1=536870911$ | N | |
| 8 | 31 | $2^{31}-1=2147483647$ | Y |
以下仅列出梅森素数
| No. | $p$ | $M_p$ | Value |
|---|---|---|---|
| 9 | 61 | $2^{61}-1$ | 2305843009213693951 |
| 10 | 89 | $2^{89}-1$ | 618970019642690137449562111 |
| 11 | 107 | $2^{107}-1$ | 162259276829213363391578010288127 |
| 12 | 127 | $2^{127}-1$ | 170141183460469231731687303715884105727 |
| 13 | 521 | $2^{521}-1$ | |
| 14 | 607 | $2^{607}-1$ | |
| 15 | 1279 | $2^{1279}-1$ | |
| 16 | 2203 | $2^{2203}-1$ | |
| 17 | 2281 | $2^{2281}-1$ | |
| 18 | 3217 | $2^{3217}-1$ | |
| 19 | 4253 | $2^{4253}-1$ | |
| 20 | 4423 | $2^{4423}-1$ |
使用 Calculator.exe 验证: isprime(2^3217-1)
>> isprime(2^3217-1)
in> isprime(2^3217-1)
in> 2^3217-1
out> 259117086013202627776246767922441530941818887553125427303974923161874019266586362086201209516800483406550695241733194177441689509238807017410377709597512042313066624082916353517952311186154862265604547691127595848775610568757931191017711408826252153849035830401185072116424747461823031471398340229288074545677907941037288235820705892351068433882986888616658650280927692080339605869308790500409503709875902119018371991620994002568935113136548829739112656797303241986517250116412703509705427773477972349821676443446668383119322540099648994051790241624056519054483690809616061625743042361721863339415852426431208737266591962061753535748892894599629195183082621860853400937932839420261866586142503251450773096274235376822938649407127700846077124211823080804139298087057504713825264571448379371125032081826126566649084251699453951887789613650248405739378594599444335231188280123660406262468609212150349937584782292237144339628858485938215738821232393687046160677362909315071
2^3217-1 is a Mersenne number, we use Lucas-Lehmer test.
2^3217-1 is a Mersenne prime.
------------------------
用时大约3分钟
References:
https://www.mersenne.org/primes/